package com.dyz.leetcode;

public class NumTrees96 {
    //动态规划
    //f(i) 以第i个数字为根结点的结果个数
    //G(n) = f(1) + f(2) + ....f(
    //f(i)=G(i-1)*G(n-i)
    //G(n) = G(0)*G(n-1)+G(2)*G(n-2)+...+G(n-1)*G(0)
    public int numTrees(int n) {
        if(n==0){return 1;}
        if(n==1){return 1;}
        int [] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            for (int j=1;j<=i;j++){
                //G(i) = f(j-1)*f(n-j)
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
        //G(n) = G(0)*G(n-1)+G(2)*G(n-2)+...+G(n-1)*G(0)
        return dp[n];

    }
}
